
<!DOCTYPE html>
<html lang="en" class="loading">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
    <title>回朔 - weifan</title>
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="google" content="notranslate" />
    <meta name="keywords" content="TriDiamond Obsidian,"> 
    <meta name="description" content="回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当,"> 
    <meta name="author" content="weifan"> 
    <link rel="alternative" href="atom.xml" title="weifan" type="application/atom+xml"> 
    <link rel="icon" href="/img/favicon.png"> 
    <link href="https://fonts.loli.net/css?family=Roboto+Mono|Rubik&display=swap" rel="stylesheet">
    
<link rel="stylesheet" href="//at.alicdn.com/t/font_1429596_nzgqgvnmkjb.css">

    
<link rel="stylesheet" href="//cdn.bootcss.com/animate.css/3.7.2/animate.min.css">

    
<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/social-share.js/1.0.16/css/share.min.css">

    
<link rel="stylesheet" href="//cdn.bootcss.com/codemirror/5.48.4/codemirror.min.css">

    
<link rel="stylesheet" href="//cdn.bootcss.com/codemirror/5.48.4/theme/dracula.css">

    
<link rel="stylesheet" href="/css/obsidian.css">

    
<link rel="stylesheet" href="/css/ball-atom.min.css">

<meta name="generator" content="Hexo 4.2.1"></head>


<body class="loading">
    <div class="loader">
        <div class="la-ball-atom la-2x">
            <div></div>
            <div></div>
            <div></div>
            <div></div>
        </div>
    </div>
    <span id="config-title" style="display:none">weifan</span>
    <div id="loader"></div>
    <div id="single">
    <div class="scrollbar gradient-bg-rev"></div>
<div id="top" style="display: block;">
    <div class="bar" style="width: 0;"></div>
    <div class="navigation animated fadeIn fast delay-1s">
        <img id="home-icon" class="icon-home" src="/img/favicon.png" alt="" data-url="https://wifidu.gitee.io">
        <div id="play-icon" title="Play/Pause" class="iconfont icon-play"></div>
        <h3 class="subtitle">回朔</h3>
        <div class="social">
            <!--        <div class="like-icon">-->
            <!--            <a href="javascript:;" class="likeThis active"><span class="icon-like"></span><span class="count">76</span></a>-->
            <!--        </div>-->
            <div>
                <div class="share">
                    
                        <a href="javascript:;" class="iconfont icon-share1"></a>
                        <div class="share-component-cc" data-disabled="facebook,douban,linkedin,diandian,tencent,google"></div>
                    
                </div>
            </div>
        </div>
    </div>
</div>

    <div class="section">
        <div class=article-header-wrapper>
    <div class="article-header">
        <div class="article-cover animated fadeIn" style="
            animation-delay: 600ms;
            animation-duration: 1.2s;
            background-image: 
                radial-gradient(ellipse closest-side, rgba(0, 0, 0, 0.65), #100e17),
                url(/img/cover.jpg) ">
        </div>
        <div class="else">
            <p class="animated fadeInDown">
                
                <a href="/categories/算法"><b>「
                    </b>算法<b> 」</b></a>
                
                June 14, 2020
            </p>
            <h3 class="post-title animated fadeInDown"><a href="/2020/06/14/%E5%9B%9E%E6%9C%94/" title="回朔" class="">回朔</a>
            </h3>
            
            <p class="post-count animated fadeInDown">
                
                <span>
                    <b class="iconfont icon-text2"></b> <i>Words count</i>
                    5.4k
                </span>
                
                
                <span>
                    <b class="iconfont icon-timer__s"></b> <i>Reading time</i>
                    5 mins.
                </span>
                
                
                
                <span id="busuanzi_container_page_pv">
                    <b class="iconfont icon-read"></b> <i>Read count</i>
                    <span id="busuanzi_value_page_pv">0</span>
                </span>
                
            </p>
            
            
            <ul class="animated fadeInDown post-tags-list" itemprop="keywords"><li class="animated fadeInDown post-tags-list-item"><a class="animated fadeInDown post-tags-list-link" href="/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a></li></ul>
            
        </div>
    </div>
</div>

<div class="screen-gradient-after">
    <div class="screen-gradient-content">
        <div class="screen-gradient-content-inside">
            <div class="bold-underline-links screen-gradient-sponsor">
                <p>
                    <span class="animated fadeIn delay-1s"></span>
                </p>
            </div>
        </div>
    </div>
</div>

<div class="article">
    <div class='main'>
        <div class="content markdown animated fadeIn">
            <p>回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。</p>
<p>回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。</p>
<h2 id="子集"><a href="#子集" class="headerlink" title="子集"></a>子集</h2><p>给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。</p>
<p>说明：解集不能包含重复的子集。</p>
<pre><code>示例:

输入: nums = [1,2,3]
输出:
[
  [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
]</code></pre><h3 id="题解"><a href="#题解" class="headerlink" title="题解"></a>题解</h3><p><strong>算法</strong></p>
<blockquote>
<p>幂集是所有长度从 0 到 n 所有子集的组合。</p>
</blockquote>
<p>根据定义，该问题可以看作是从序列中生成幂集。</p>
<p>遍历 子集长度，通过 回溯 生成所有给定长度的子集。</p>
<p><img src="/img/combinations.png" alt="combinations"></p>
<blockquote>
<p>回溯法是一种探索所有潜在可能性找到解决方案的算法。如果当前方案不是正确的解决方案，或者不是最后一个正确的解决方案，则回溯法通过修改上一步的值继续寻找解决方案。</p>
</blockquote>
<p><img src="/img/backtracking.png" alt="backtracking"></p>
<p>算法</p>
<p>定义一个回溯方法 <code>backtrack(first, curr)</code>，第一个参数为索引 first，第二个参数为当前子集 curr。</p>
<ul>
<li><p>如果当前子集构造完成，将它添加到输出集合中。</p>
</li>
<li><p>否则，从 <code>first</code> 到 <code>n</code> 遍历索引 <code>i</code>。</p>
<ul>
<li><p>将整数 <code>nums[i]</code> 添加到当前子集 <code>curr</code>。</p>
</li>
<li><p>继续向子集中添加整数：backtrack(i + 1, curr)。</p>
</li>
<li><p>从 curr 中删除 nums[i] 进行回溯。</p>
</li>
</ul>
</li>
</ul>
<pre><code class="java">class Solution {
  List&lt;List&lt;Integer&gt;&gt; output = new ArrayList();
  int n, k;

  public void backtrack(int first, ArrayList&lt;Integer&gt; curr, int[] nums) {
    // if the combination is done
    if (curr.size() == k)
      output.add(new ArrayList(curr));

    for (int i = first; i &lt; n; ++i) {
      // add i into the current combination
      curr.add(nums[i]);
      // use next integers to complete the combination
      backtrack(i + 1, curr, nums);
      // backtrack
      curr.remove(curr.size() - 1);
    }
  }

  public List&lt;List&lt;Integer&gt;&gt; subsets(int[] nums) {
    n = nums.length;
    for (k = 0; k &lt; n + 1; ++k) {
      backtrack(0, new ArrayList&lt;Integer&gt;(), nums);
    }
    return output;
  }
}</code></pre>
<pre><code class="php">class Solution {
    protected  $output = [];
    protected  $k;
    protected  $n;
     /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function subsets($nums) {
        $this-&gt;n = count($nums);

        for ($this-&gt;k = 0; $this-&gt;k &lt; $this-&gt;n + 1; ++$this-&gt;k) {
            $this-&gt;backtrack(0, [], $nums);
        }

        return $this-&gt;output;
    }

    function backtrack(int $first, array $curr, array $nums)
    {
        if (count($curr) == $this-&gt;k) {
            array_push($this-&gt;output, $curr);
            return;
        }

        for ($i = $first; $i &lt; $this-&gt;n; $i ++) {
            array_push($curr, $nums[$i]);

            $this-&gt;backtrack($i + 1, $curr, $nums);

            array_pop($curr);
        }
    }
}</code></pre>
<p>复杂度分析</p>
<p>时间复杂: O(N * 2^N)，生成所有子集，并复制到输出集合中。</p>
<p>空间复杂度：O(N * 2^N)，存储所有子集，共 n 个元素，每个元素都有可能存在或者不存在。</p>
<p>来源：<a href="https://leetcode-cn.com/problems/subsets" target="_blank" rel="noopener"> 力扣（LeetCode） </a></p>
<h2 id="组合总和"><a href="#组合总和" class="headerlink" title="组合总和"></a>组合总和</h2><p>给定一个无重复元素的数组 <code>candidates</code> 和一个目标数 <code>target</code> ，找出 <code>candidates</code> 中所有可以使数字和为 <code>target</code> 的组合。</p>
<p><code>candidates</code> 中的数字可以无限制重复被选取。</p>
<p><strong>说明：</strong></p>
<ul>
<li>所有数字（包括 target）都是正整数。</li>
<li>解集不能包含重复的组合。</li>
</ul>
<p><strong>示例 1:</strong></p>
<pre><code>输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]</code></pre><p><strong>示例 2:</strong></p>
<pre><code>输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]</code></pre><h3 id="题解-1"><a href="#题解-1" class="headerlink" title="题解"></a>题解</h3><pre><code class="python">from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -&gt; List[List[int]]:
        size = len(candidates)
        if size == 0:
            return []

        # 剪枝是为了提速，在本题非必需
        candidates.sort()
        # 在遍历的过程中记录路径，它是一个栈
        path = []
        res = []
        # 注意要传入 size ，在 range 中， size 取不到
        self.__dfs(candidates, 0, size, path, res, target)
        return res

    def __dfs(self, candidates, begin, size, path, res, target):
        # 先写递归终止的情况
        if target == 0:
            # Python 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
            # 或者使用 path.copy()
            res.append(path[:])
            return

        for index in range(begin, size):
            residue = target - candidates[index]
            # “剪枝”操作，不必递归到下一层，并且后面的分支也不必执行
            if residue &lt; 0:
                break
            path.append(candidates[index])
            # 因为下一层不能比上一层还小，起始索引还从 index 开始
            self.__dfs(candidates, index, size, path, res, residue)
            path.pop()


if __name__ == &#39;__main__&#39;:
    candidates = [2, 3, 6, 7]
    target = 7
    solution = Solution()
    result = solution.combinationSum(candidates, target)
    print(result)
</code></pre>
<blockquote>
<p><a href="https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/" target="_blank" rel="noopener">link</a></p>
</blockquote>

            <!--[if lt IE 9]><script>document.createElement('audio');</script><![endif]-->
            <audio id="audio" loop="1" preload="auto" controls="controls"
                data-autoplay="false">
                <source type="audio/mpeg" src="">
            </audio>
            
            <ul id="audio-list" style="display:none">
                
                
                <li title='0' data-url='/statics/chengdu.mp3'></li>
                
                    
            </ul>
            
            
            
    <div id='gitalk-container' class="comment link"
        data-ae='true'
        data-ci='ec894e2b66f752e8b7fb'
        data-cs='3ccc2e92bb350688fe2c2dc2930189b62622bfb1'
        data-r='blog-comments'
        data-o='TriDiamond'
        data-a='TriDiamond'
        data-d=''
    >Comments</div>


            
            
        </div>
        <div class="sidebar">
            <div class="box animated fadeInRight">
                <div class="subbox">
                    <img src="/img/mei.jpeg" height=300 width=300></img>
                    <p>weifan</p>
                    <span>Think like an artist, develop like an artisan</span>
                    <dl>
                        <dd><a href="https://github.com/wifidu" target="_blank"><span
                                    class=" iconfont icon-github"></span></a></dd>
                        <dd><a href="" target="_blank"><span
                                    class=" iconfont icon-twitter"></span></a></dd>
                        <dd><a href="" target="_blank"><span
                                    class=" iconfont icon-stack-overflow"></span></a></dd>
                    </dl>
                </div>
                <ul>
                    <li><a href="/">7 <p>Articles</p></a></li>
                    <li><a href="/categories">6 <p>Categories</p></a></li>
                    <li><a href="/tags">6 <p>Tags</p></a></li>
                </ul>
            </div>
            
            
            
            <div class="box sticky animated fadeInRight faster">
                <div id="toc" class="subbox">
                    <h4>Contents</h4>
                    <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#子集"><span class="toc-number">1.</span> <span class="toc-text">子集</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#题解"><span class="toc-number">1.1.</span> <span class="toc-text">题解</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#组合总和"><span class="toc-number">2.</span> <span class="toc-text">组合总和</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#题解-1"><span class="toc-number">2.1.</span> <span class="toc-text">题解</span></a></li></ol></li></ol>
                </div>
            </div>
            
            
        </div>
    </div>
</div>

    </div>
</div>
    <div id="back-to-top" class="animated fadeIn faster">
        <div class="flow"></div>
        <span class="percentage animated fadeIn faster">0%</span>
        <span class="iconfont icon-top02 animated fadeIn faster"></span>
    </div>
</body>
<footer>
    <p class="copyright" id="copyright">
        &copy; 2020
        <span class="gradient-text">
            weifan
        </span>.
        Powered by <a href="http://hexo.io/" title="Hexo" target="_blank" rel="noopener">Hexo</a>
        Theme
        <span class="gradient-text">
            <a href="https://github.com/TriDiamond/hexo-theme-obsidian" title="Obsidian" target="_blank" rel="noopener">Obsidian</a>
        </span>
        <small><a href="https://github.com/TriDiamond/hexo-theme-obsidian/blob/master/CHANGELOG.md" title="v1.4.3" target="_blank" rel="noopener">v1.4.3</a></small>
    </p>
</footer>

<script type="text/javascript" src="https://cdn.bootcss.com/mathjax/2.7.6/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script>
  MathJax.Hub.Config({
    "HTML-CSS": {
      preferredFont: "TeX",
      availableFonts: ["STIX", "TeX"],
      linebreaks: {
        automatic: true
      },
      EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
      inlineMath: [
        ["$", "$"],
        ["\\(", "\\)"]
      ],
      processEscapes: true,
      ignoreClass: "tex2jax_ignore|dno",
      skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
      noUndefined: {
        attributes: {
          mathcolor: "red",
          mathbackground: "#FFEEEE",
          mathsize: "90%"
        }
      },
      Macros: {
        href: "{}"
      }
    },
    messageStyle: "none"
  });
</script>
<script>
  function initialMathJax() {
    MathJax.Hub.Queue(function () {
      var all = MathJax.Hub.getAllJax(),
        i;
      // console.log(all);
      for (i = 0; i < all.length; i += 1) {
        console.log(all[i].SourceElement().parentNode)
        all[i].SourceElement().parentNode.className += ' has-jax';
      }
    });
  }

  function reprocessMathJax() {
    if (typeof MathJax !== 'undefined') {
      MathJax.Hub.Queue(["Typeset", MathJax.Hub]);
    }
  }
</script>



    
<link rel="stylesheet" href="//cdn.bootcss.com/gitalk/1.5.0/gitalk.min.css">

    
<script src="//cdn.bootcss.com/gitalk/1.5.0/gitalk.min.js"></script>



<script src="//cdnjs.cloudflare.com/ajax/libs/jquery/3.4.1/jquery.min.js"></script>
<script src="/js/plugin.js"></script>
<script src="/js/obsidian.js"></script>
<script src="/js/jquery.truncate.js"></script>
<script src="/js/search.js"></script>


<script src="//cdn.bootcss.com/typed.js/2.0.10/typed.min.js"></script>


<script src="//cdn.bootcss.com/blueimp-md5/2.12.0/js/md5.min.js"></script>


<script src="//cdnjs.cloudflare.com/ajax/libs/social-share.js/1.0.16/js/social-share.min.js"></script>


<script src="https://cdn.bootcss.com/codemirror/5.48.4/codemirror.min.js"></script>

    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/javascript/javascript.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/css/css.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/xml/xml.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/htmlmixed/htmlmixed.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/clike/clike.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/php/php.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/shell/shell.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/python/python.min.js"></script>




    
<script src="/js/busuanzi.min.js"></script>

    <script>
        $(document).ready(function () {
            if ($('span[id^="busuanzi_"]').length) {
                initialBusuanzi();
            }
        });
    </script>



<link rel="stylesheet" href="//cdn.bootcss.com/photoswipe/4.1.3/photoswipe.min.css">
<link rel="stylesheet" href="//cdn.bootcss.com/photoswipe/4.1.3/default-skin/default-skin.min.css">


<script src="//cdn.bootcss.com/photoswipe/4.1.3/photoswipe.min.js"></script>
<script src="//cdn.bootcss.com/photoswipe/4.1.3/photoswipe-ui-default.min.js"></script>


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">
    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>
    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">
        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>
        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">
            <div class="pswp__top-bar">
                <!--  Controls are self-explanatory. Order can be changed. -->
                <div class="pswp__counter"></div>
                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
                <button class="pswp__button pswp__button--share" title="Share"></button>
                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                      <div class="pswp__preloader__cut">
                        <div class="pswp__preloader__donut"></div>
                      </div>
                    </div>
                </div>
            </div>
            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div> 
            </div>
            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>
            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>
            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>
        </div>
    </div>
</div>



    <!-- Global site tag (gtag.js) - Google Analytics -->
    <script async src="//www.googletagmanager.com/gtag/js?id=UA-149874671-1"></script>
    <script>
        window.dataLayer = window.dataLayer || [];
        function gtag(){dataLayer.push(arguments);}
        gtag('js', new Date());

        gtag('config', 'UA-149874671-1');
    </script>





<script>
    function initialTyped () {
        var typedTextEl = $('.typed-text');
        if (typedTextEl && typedTextEl.length > 0) {
            var typed = new Typed('.typed-text', {
                strings: ["Think like an artist, develop like an artisan", "艺术家思维去思考问题，工匠创造精神去开发"],
                typeSpeed: 90,
                loop: true,
                loopCount: Infinity,
                backSpeed: 20,
            });
        }
    }

    if ($('.article-header') && $('.article-header').length) {
        $(document).ready(function () {
            initialTyped();
        });
    }
</script>




</html>
